--树
--[[
	前序遍历 根节点->左子树->右子树
	中序遍历 左子树->根节点->右
	后序遍历 左->右->根
]]

require "functions"
local QTree = class("QTree")

function QTree:ctor()
	self.root = nil
	self.curNode = nil
end

function QTree:createNode(value)
	if not value then return end
	local node = {
		left = nil,
		right = nil,
		value = value,
	}
	return node
end

function QTree:createTree(tb)
	for k,v in pairs(tb) do 
		if not self.root then 
			self.root = self:createNode(v[1])
			self.curNode = self.root
		else
			local node1 = self:createNode(v[1])
			local node2 = self:createNode(v[2])
			local lr = v[3]
			self.curNode.left = node1
			self.curNode.right = node2			
			self.curNode = node1
			if lr == 2 then 
				self.curNode = node2
			end

		end
	end
end

function QTree:frontIter(node)
	if not node then return end
	print(node.value)
	self:frontIter(node.left)
	self:frontIter(node.right)
end

function QTree:middleIter(node)
	if not node then return end
	self:middleIter(node.left)
	print(node.value)
	self:middleIter(node.right)
end

function QTree:afterIter(node)
	if not node then return end
	
	self:afterIter(node.left)
	self:afterIter(node.right)
	print(node.value)
end

local tb = {{2},{3,4,2},{5,6,2},{7,8}}
local tree = QTree.new()
tree:createTree(tb)
print("_____前序遍历_______")
tree:frontIter(tree.root)
print("______中______")
tree:middleIter(tree.root)
print("_______后_____")
tree:afterIter(tree.root)

--[[------------------------
-- 基于一个table的二叉树
tree = {}
 
function create_tree(key,data)
    if not tree.root then
        local node = create_node(key,data)
        tree.root=node -- 创建一个新的节点 设置为root
    end
end
 
 
function create_node(key,data)
    local node = {lchild=nil,rchild=nil,key=key,data=data }
    return node
end
 
function put(key,data,node)
 
    if key<node.key then
        if node.left then
            -- 如果有左节点 则递归子节点
            return put(key,data,node.left)
        else
            -- 如果没有子节点了 创造新节点
            node.left = create_node(key,data)
        end
    else
        if key>node.key then
            if node.right then
                return put(key,data,node.right)
            else
                node.right = create_node(key,data)
            end
        else
            -- key==node.key时 --也就是出现重复的关键码时
            if not node.other then
                node.other={}
                node.other.index =0
            end
            node.other.index=node.other.index+1
            node.other[node.other.index] = data
        end
    end
end
 
function search(root,key)
    -- 从根部root节点 开始搜索 key
    if key==root.key then
        return root
    end
 
    -- 下面是两个递归 但是如果 不存在key呢
    if key<root.key then
        if not root.left then
            print("范围内 没有这个"..key)
        end
        return search(root.left,key)
    end
 
    if key>root.key then
        if not root.right then
            print("范围内没有这个"..key)
        end
        return search(root.right,key)
    end
end
 
 
create_tree(1,"根节点")
for i =2,100 do
    put(i,"这是第"..i.."号元素",tree.root)
end
 
for i =1,100 do
    print(search(tree.root,i).data)
end
 


--]]